package 算法基础模板.chapter_04;

import com.sun.media.sound.RIFFInvalidDataException;
import com.sun.xml.internal.fastinfoset.stax.factory.StAXOutputFactory;

import java.util.Arrays;

/**
 * 质数: 大于1 的整数, 如果只包含1 和本身这两个约束, 就是质数
 *
 * @author Summerday
 */
public class PrimeT {



    /**
     * 最暴力的试除 o(n)
     */
    boolean isPrime (int n) {
        if (n < 2) return false;
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    // 两个约数 成对出现, 枚举一半  不推荐 i * i < n 的写法  溢出
    boolean isPrime2 (int n) {
        if (n < 2) return false;
        for (int i = 2; i <= n / i; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    int primes[] = new int[10000];
    boolean st[] = new boolean[10000];
    int cnt;
    // 筛素数 (n / 2 + n / 3 + ... + n / n) 调和级数 ln N + c   约等于nlnN 
    void getPrimes (int n) {
        for (int i = 2; i <= n; i++ ){
            if (!st[i]) primes[cnt ++] = n;
            for(int j = i + 1; j <= n; j += i) st[j] = true;
        }
    }

    // 埃氏
    void getPrimes2 (int n) {
        for (int i = 2; i <= n; i++ ){
            if (!st[i]) primes[cnt ++] = i;
            for(int j = 0; primes[j] <= n / i; j ++) {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
        for(int i = 0; i < cnt;  i ++){
            System.out.print(primes[i] + " ");
        }
        System.out.printf("cnt : %d", cnt);
    }

    public static void main (String[] args) {
        new PrimeT().getPrimes2(100);
    }

}
